/*
 * @lc app=leetcode.cn id=662 lang=golang
 *
 * [662] 二叉树最大宽度
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func widthOfBinaryTree(root *TreeNode) int {
	maxWidth := 0
	if root == nil {
		return maxWidth
	}
	maxWidth = 1
	nqueue := []*TreeNode{}
	iqueue := []int{}
	size := 1
	nqueue = append(nqueue, root)
	iqueue = append(iqueue, 0)
	for len(nqueue) != 0 {
		node := nqueue[0]
		nqueue = nqueue[1:]
		index := iqueue[0]
		iqueue = iqueue[1:]
		size--
		if node.Left != nil {
			nqueue = append(nqueue, node.Left)
			iqueue = append(iqueue, index*2+1)
		}

		if node.Right != nil {
			nqueue = append(nqueue, node.Right)
			iqueue = append(iqueue, index*2+2)
		}

		if size == 0 {
			if len(nqueue) >= 2 {
				maxWidth = max(maxWidth, iqueue[len(iqueue)-1]-iqueue[0]+1)
			}
			size = len(nqueue)
		}
	}

	return maxWidth
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

// @lc code=end

